from typing import List


class Solution:
    def dfs(self, nums, s, e, path, res, st):
        if s > e:
            res.append(path.copy())
            return
        for i in range(len(nums)):
            if not st[i]:
                path[s] = nums[i]
                st[i] = True
                self.dfs(nums, s + 1, e, path, res, st)
                st[i] = False
        return

    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = [0]*len(nums)
        st = [False] * len(nums)
        self.dfs(nums, 0, len(nums) - 1, path, res, st)
        return res


t = Solution().permute([1, 2, 3])
print(t)